Search Results

Documents authored by Adamczyk, Marek

Document
DOI: 10.4230/LIPIcs.ESA.2019.1
Constant-Factor FPT Approximation for Capacitated k-Median

Authors: Marek Adamczyk, Jarosław Byrka, Jan Marcinkowski, Syed M. Meesum, and Michał Włodarczyk

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Capacitated k-median is one of the few outstanding optimization problems for which the existence of a polynomial time constant factor approximation algorithm remains an open problem. In a series of recent papers algorithms producing solutions violating either the number of facilities or the capacity by a multiplicative factor were obtained. However, to produce solutions without violations appears to be hard and potentially requires different algorithmic techniques. Notably, if parameterized by the number of facilities k, the problem is also W[2] hard, making the existence of an exact FPT algorithm unlikely. In this work we provide an FPT-time constant factor approximation algorithm preserving both cardinality and capacity of the facilities. The algorithm runs in time 2^O(k log k) n^O(1) and achieves an approximation ratio of 7+epsilon.
Cite as

Marek Adamczyk, Jarosław Byrka, Jan Marcinkowski, Syed M. Meesum, and Michał Włodarczyk. Constant-Factor FPT Approximation for Capacitated k-Median. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{adamczyk_et_al:LIPIcs.ESA.2019.1,
  author =	{Adamczyk, Marek and Byrka, Jaros{\l}aw and Marcinkowski, Jan and Meesum, Syed M. and W{\l}odarczyk, Micha{\l}},
  title =	{{Constant-Factor FPT Approximation for Capacitated k-Median}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.1},
  URN =		{urn:nbn:de:0030-drops-111225},
  doi =		{10.4230/LIPIcs.ESA.2019.1},
  annote =	{Keywords: K-median, Clustering, Approximation Algorithms, Fixed Parameter Tractability}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.35
When the Optimum is also Blind: a New Perspective on Universal Optimization

Authors: Marek Adamczyk, Fabrizio Grandoni, Stefano Leonardi, and Michal Wlodarczyk

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Consider the following variant of the set cover problem. We are given a universe U={1,...,n} and a collection of subsets C = {S_1,...,S_m} where each S_i is a subset of U. For every element u from U we need to find a set phi(u) from collection C such that u belongs to phi(u). Once we construct and fix the mapping phi from U to C a subset X from the universe U is revealed, and we need to cover all elements from X with exactly phi(X), that is {phi(u)}_{all u from X}. The goal is to find a mapping such that the cover phi(X) is as cheap as possible. This is an example of a universal problem where the solution has to be created before the actual instance to deal with is revealed. Such problems appear naturally in some settings when we need to optimize under uncertainty and it may be actually too expensive to begin finding a good solution once the input starts being revealed. A rich body of work was devoted to investigate such problems under the regime of worst case analysis, i.e., when we measure how good the solution is by looking at the worst-case ratio: universal solution for a given instance vs optimum solution for the same instance. As the universal solution is significantly more constrained, it is typical that such a worst-case ratio is actually quite big. One way to give a viewpoint on the problem that would be less vulnerable to such extreme worst-cases is to assume that the instance, for which we will have to create a solution, will be drawn randomly from some probability distribution. In this case one wants to minimize the expected value of the ratio: universal solution vs optimum solution. Here the bounds obtained are indeed smaller than when we compare to the worst-case ratio. But even in this case we still compare apples to oranges as no universal solution is able to construct the optimum solution for every possible instance. What if we would compare our approximate universal solution against an optimal universal solution that obeys the same rules as we do? We show that under this viewpoint, but still in the stochastic variant, we can indeed obtain better bounds than in the expected ratio model. For example, for the set cover problem we obtain $H_n$ approximation which matches the approximation ratio from the classic deterministic setup. Moreover, we show this for all possible probability distributions over $U$ that have a polynomially large carrier, while all previous results pertained to a model in which elements were sampled independently. Our result is based on rounding a proper configuration IP that captures the optimal universal solution, and using tools from submodular optimization. The same basic approach leads to improved approximation algorithms for other related problems, including Vertex Cover, Edge Cover, Directed Steiner Tree, Multicut, and Facility Location.
Cite as

Marek Adamczyk, Fabrizio Grandoni, Stefano Leonardi, and Michal Wlodarczyk. When the Optimum is also Blind: a New Perspective on Universal Optimization. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{adamczyk_et_al:LIPIcs.ICALP.2017.35,
  author =	{Adamczyk, Marek and Grandoni, Fabrizio and Leonardi, Stefano and Wlodarczyk, Michal},
  title =	{{When the Optimum is also Blind: a New Perspective on Universal Optimization}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.35},
  URN =		{urn:nbn:de:0030-drops-74436},
  doi =		{10.4230/LIPIcs.ICALP.2017.35},
  annote =	{Keywords: approximation algorithms, stochastic optimization, submodularity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.29
Submodular Stochastic Probing on Matroids

Authors: Marek Adamczyk, Maxim Sviridenko, and Justin Ward

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
In a stochastic probing problem we are given a universe E, where each element e in E is active independently with probability p in [0,1], and only a probe of e can tell us whether it is active or not. On this universe we execute a process that one by one probes elements - if a probed element is active, then we have to include it in the solution, which we gradually construct. Throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. This abstract model was presented in [Gupta and Nagaraja, IPCO 2013], and provides a unified view of a number of problems. Thus far all the results in this general framework pertain only to the case in which we are maximizing a linear objective function of the successfully probed elements. In this paper we generalize the stochastic probing problem by considering a monotone submodular objective function. We give a (1-1/e)/(k_in+k_out+1)-approximation algorithm for the case in which we are given k_in greater than 0 matroids as inner constraints and k_out greater than 1 matroids as outer constraints. There are two main ingredients behind this result. First is a previously unpublished stronger bound on the continuous greedy algorithm due to Vondrak. Second is a rounding procedure that also allows us to obtain an improved 1/(k_in+k_out)-approximation for linear objective functions.
Cite as

Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular Stochastic Probing on Matroids. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 29-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{adamczyk_et_al:LIPIcs.STACS.2014.29,
  author =	{Adamczyk, Marek and Sviridenko, Maxim and Ward, Justin},
  title =	{{Submodular Stochastic Probing on Matroids}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{29--40},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.29},
  URN =		{urn:nbn:de:0030-drops-44445},
  doi =		{10.4230/LIPIcs.STACS.2014.29},
  annote =	{Keywords: approximation algorithms, stochastic optimization, submodular optimization, matroids, iterative rounding}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact